<!DOCTYPE html>
<!-- saved from url=(0079)https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#conservative-gc -->
<html lang="en-AU"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <script type="text/javascript" src="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/OtAutoBlock.js.下载"></script>
    

    
    <meta content="IE=edge" http-equiv="X-UA-Compatible">
    <meta content="width=device-width, initial-scale=1" name="viewport"> <!-- Favicons --> <link rel="apple-touch-icon" sizes="180x180" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/apple-touch-icon.png">

    

    <link rel="icon" type="image/png" sizes="32x32" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/favicon-32x32.png">
    <link rel="icon" type="image/png" sizes="16x16" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/favicon-16x16.png">
    <link rel="manifest" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/site.webmanifest">
    <link rel="mask-icon" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/safari-pinned-tab.svg" color="#be830e">
    <link rel="shortcut icon" href="https://comp.anu.edu.au/courses/comp2310/assets/favicons/favicon.ico">
    <meta content="#be830e" name="msapplication-TileColor">
    <meta name="msapplication-config" content="/courses/comp2310/assets/favicons/browserconfig.xml">
    <meta content="#ffffff" name="theme-color"> <!-- Begin Jekyll SEO tag v2.8.0 -->
<title>Assignment 1: Malloc | Systems, Networks, and Concurrency</title>
<meta name="generator" content="Jekyll v4.3.2">
<meta property="og:title" content="Assignment 1: Malloc">
<meta property="og:locale" content="en_US">
<meta name="description" content="The course website for COMP2310">
<meta property="og:description" content="The course website for COMP2310">
<link rel="canonical" href="https://comp.anu.edu.au//courses/comp2310/assessments/01-malloc/">
<meta property="og:url" content="https://comp.anu.edu.au//courses/comp2310/assessments/01-malloc/">
<meta property="og:site_name" content="Systems, Networks, and Concurrency">
<meta property="og:image" content="https://comp.anu.edu.au//courses/comp2310/assets/images/datacenter.jpeg">
<meta property="og:type" content="article">
<meta property="article:published_time" content="2024-11-07T04:48:03+00:00">
<meta name="twitter:card" content="summary_large_image">
<meta property="twitter:image" content="https://comp.anu.edu.au//courses/comp2310/assets/images/datacenter.jpeg">
<meta property="twitter:title" content="Assignment 1: Malloc">
<script type="application/ld+json">
{"@context":"https://schema.org","@type":"BlogPosting","dateModified":"2024-11-07T04:48:03+00:00","datePublished":"2024-11-07T04:48:03+00:00","description":"The course website for COMP2310","headline":"Assignment 1: Malloc","image":"https://comp.anu.edu.au//courses/comp2310/assets/images/datacenter.jpeg","mainEntityOfPage":{"@type":"WebPage","@id":"https://comp.anu.edu.au//courses/comp2310/assessments/01-malloc/"},"url":"https://comp.anu.edu.au//courses/comp2310/assessments/01-malloc/"}</script>
<!-- End Jekyll SEO tag -->
 <link href="https://fonts.gstatic.com/" rel="preconnect">
    <link href="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/css2" rel="stylesheet">
    <link rel="stylesheet" href="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/styles.css">
    
    
      

<script id="MathJax-script" async="" src="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/tex-mml-chtml.js.下载"></script>

    
    
  <style type="text/css">.CtxtMenu_InfoClose {  top:.2em; right:.2em;}
.CtxtMenu_InfoContent {  overflow:auto; text-align:left; font-size:80%;  padding:.4em .6em; border:1px inset; margin:1em 0px;  max-height:20em; max-width:30em; background-color:#EEEEEE;  white-space:normal;}
.CtxtMenu_Info.CtxtMenu_MousePost {outline:none;}
.CtxtMenu_Info {  position:fixed; left:50%; width:auto; text-align:center;  border:3px outset; padding:1em 2em; background-color:#DDDDDD;  color:black;  cursor:default; font-family:message-box; font-size:120%;  font-style:normal; text-indent:0; text-transform:none;  line-height:normal; letter-spacing:normal; word-spacing:normal;  word-wrap:normal; white-space:nowrap; float:none; z-index:201;  border-radius: 15px;                     /* Opera 10.5 and IE9 */  -webkit-border-radius:15px;               /* Safari and Chrome */  -moz-border-radius:15px;                  /* Firefox */  -khtml-border-radius:15px;                /* Konqueror */  box-shadow:0px 10px 20px #808080;         /* Opera 10.5 and IE9 */  -webkit-box-shadow:0px 10px 20px #808080; /* Safari 3 & Chrome */  -moz-box-shadow:0px 10px 20px #808080;    /* Forefox 3.5 */  -khtml-box-shadow:0px 10px 20px #808080;  /* Konqueror */  filter:progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color="gray", Positive="true"); /* IE */}
</style><style type="text/css">.CtxtMenu_MenuClose {  position:absolute;  cursor:pointer;  display:inline-block;  border:2px solid #AAA;  border-radius:18px;  -webkit-border-radius: 18px;             /* Safari and Chrome */  -moz-border-radius: 18px;                /* Firefox */  -khtml-border-radius: 18px;              /* Konqueror */  font-family: "Courier New", Courier;  font-size:24px;  color:#F0F0F0}
.CtxtMenu_MenuClose span {  display:block; background-color:#AAA; border:1.5px solid;  border-radius:18px;  -webkit-border-radius: 18px;             /* Safari and Chrome */  -moz-border-radius: 18px;                /* Firefox */  -khtml-border-radius: 18px;              /* Konqueror */  line-height:0;  padding:8px 0 6px     /* may need to be browser-specific */}
.CtxtMenu_MenuClose:hover {  color:white!important;  border:2px solid #CCC!important}
.CtxtMenu_MenuClose:hover span {  background-color:#CCC!important}
.CtxtMenu_MenuClose:hover:focus {  outline:none}
</style><style type="text/css">.CtxtMenu_Menu {  position:absolute;  background-color:white;  color:black;  width:auto; padding:5px 0px;  border:1px solid #CCCCCC; margin:0; cursor:default;  font: menu; text-align:left; text-indent:0; text-transform:none;  line-height:normal; letter-spacing:normal; word-spacing:normal;  word-wrap:normal; white-space:nowrap; float:none; z-index:201;  border-radius: 5px;                     /* Opera 10.5 and IE9 */  -webkit-border-radius: 5px;             /* Safari and Chrome */  -moz-border-radius: 5px;                /* Firefox */  -khtml-border-radius: 5px;              /* Konqueror */  box-shadow:0px 10px 20px #808080;         /* Opera 10.5 and IE9 */  -webkit-box-shadow:0px 10px 20px #808080; /* Safari 3 & Chrome */  -moz-box-shadow:0px 10px 20px #808080;    /* Forefox 3.5 */  -khtml-box-shadow:0px 10px 20px #808080;  /* Konqueror */}
.CtxtMenu_MenuItem {  padding: 1px 2em;  background:transparent;}
.CtxtMenu_MenuArrow {  position:absolute; right:.5em; padding-top:.25em; color:#666666;  font-family: null; font-size: .75em}
.CtxtMenu_MenuActive .CtxtMenu_MenuArrow {color:white}
.CtxtMenu_MenuArrow.CtxtMenu_RTL {left:.5em; right:auto}
.CtxtMenu_MenuCheck {  position:absolute; left:.7em;  font-family: null}
.CtxtMenu_MenuCheck.CtxtMenu_RTL { right:.7em; left:auto }
.CtxtMenu_MenuRadioCheck {  position:absolute; left: .7em;}
.CtxtMenu_MenuRadioCheck.CtxtMenu_RTL {  right: .7em; left:auto}
.CtxtMenu_MenuInputBox {  padding-left: 1em; right:.5em; color:#666666;  font-family: null;}
.CtxtMenu_MenuInputBox.CtxtMenu_RTL {  left: .1em;}
.CtxtMenu_MenuComboBox {  left:.1em; padding-bottom:.5em;}
.CtxtMenu_MenuSlider {  left: .1em;}
.CtxtMenu_SliderValue {  position:absolute; right:.1em; padding-top:.25em; color:#333333;  font-size: .75em}
.CtxtMenu_SliderBar {  outline: none; background: #d3d3d3}
.CtxtMenu_MenuLabel {  padding: 1px 2em 3px 1.33em;  font-style:italic}
.CtxtMenu_MenuRule {  border-top: 1px solid #DDDDDD;  margin: 4px 3px;}
.CtxtMenu_MenuDisabled {  color:GrayText}
.CtxtMenu_MenuActive {  background-color: #606872;  color: white;}
.CtxtMenu_MenuDisabled:focus {  background-color: #E8E8E8}
.CtxtMenu_MenuLabel:focus {  background-color: #E8E8E8}
.CtxtMenu_ContextMenu:focus {  outline:none}
.CtxtMenu_ContextMenu .CtxtMenu_MenuItem:focus {  outline:none}
.CtxtMenu_SelectionMenu {  position:relative; float:left;  border-bottom: none; -webkit-box-shadow:none; -webkit-border-radius:0px; }
.CtxtMenu_SelectionItem {  padding-right: 1em;}
.CtxtMenu_Selection {  right: 40%; width:50%; }
.CtxtMenu_SelectionBox {  padding: 0em; max-height:20em; max-width: none;  background-color:#FFFFFF;}
.CtxtMenu_SelectionDivider {  clear: both; border-top: 2px solid #000000;}
.CtxtMenu_Menu .CtxtMenu_MenuClose {  top:-10px; left:-10px}
</style></head>

  <body>
    

<link rel="stylesheet" href="logo.css">

<header class="header container" id="site-header">
  
  <img src="logo.png" alt="ANU Logo" class="header-logo">
  
  <a class="header__brand" href="https://comp.anu.edu.au/">
    

<span aria-label="ANU crest" class="logo-favicon" role="img"></span>
    

<span aria-label="Australian National University logo" class="logo-secondary" role="img"></span>

    
  </a>

  
  <span class="header__filler"></span>

  
  <a aria-controls="nav-menu" aria-expanded="false" aria-haspopup="dialog" class="header__nav-toggle icon-link" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#nav-menu" id="nav-toggle" role="button">
    <span class="visually-hidden">Open main menu</span>
    <span aria-hidden="true"><svg class="icon"><use xlink:href="#fas.fa-bars"></use></svg></span>
  </a>

  
  <a aria-controls="search-menu" aria-expanded="false" aria-haspopup="dialog" class="header__search-toggle icon-link" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#search-menu" id="search-toggle" role="button">
    <span class="visually-hidden">Search this site</span>
    <span aria-hidden="true"><svg class="icon"><use xlink:href="#fas.fa-search"></use></svg></span>
  </a>
</header>




<script>
// Because this script will be included in the middle of the document, we wait
// for DOM content to load before binding event listeners
document.addEventListener("DOMContentLoaded", () => {
  /**
   * Nav submenu progressive enhancement JS for a11y 
   */
  const allNavSubmenuToggles = document.querySelectorAll(".nav-submenu-toggle__checkbox");

  allNavSubmenuToggles.forEach((toggle) => {
    /* Use "Enter" key on submenu toggle to open / close the submenu */
    toggle.addEventListener("keydown", (ev) => {
      if (ev.key === "Enter") {
        ev.preventDefault;
        toggle.checked = !toggle.checked;
      }
    });

    /* Close any other open submenus when one is toggled open */
    toggle.addEventListener("change", () => {
      if (toggle.checked) {
        allNavSubmenuToggles.forEach((el) => {
          if (el !== toggle && el.checked) {
            el.checked = false;
          }
        })
      }
    })
  });

  /* Use "Escape" key to close any open submenus */
  document.addEventListener("keydown", (ev) => {
    //  In Internet Explorer &  Firefox 36 and earlier, the Esc key returns "Esc" instead of "Escape".
    if (ev.key === "Escape" || ev.key === "Esc") {
      ev.preventDefault();
      allNavSubmenuToggles.forEach((toggle) => {
        if (toggle.checked) {
          toggle.checked = false;
          toggle.parentElement.querySelectorAll(".card__link").forEach((submenuLink) => {
            submenuLink.blur();
          })
        }
      });
    }
  });

  /**
   * Nav & search menu overlay panel progressive enhancement JS for a11y 
   */

  // Initialise focusableMap to store focusable elements in nav & search menus
  const focusableMap = {};

  const navMenu = document.querySelector("#nav-menu");
  const navToggle = document.querySelector("#nav-toggle");
  /* Add focusable elements in nav menu to focusableMap */
  focusableMap.nav = navMenu
    // Hacky selector but using something more general selects links that aren't
    // visible from inside the submenu
    .querySelectorAll(`
      .nav-menu__brand,
      .nav-menu__close,
      .nav-menu__menu-link,
      .nav-menu__toggle-checkbox,
      input:not([type='hidden']),
      .nav-submenu-toggle__checkbox:checked ~ .nav-submenu .nav-submenu__menu-link`
    );

  const searchMenu = document.querySelector("#search-menu");
  const searchToggle = document.querySelector("#search-toggle");
  /* Add focusable elements in search menu to focusableMap */
  focusableMap.search = searchMenu.querySelectorAll("button:not(.trap-focus), input:not([type='hidden']), [href]");

  /**
   * Contain tab order within nav & search menus by adding event listeners for
   * tabbing events on .trap-focus elements which have been placed at the start
   * and end of each of the menus.
   */
  const handleTrapFocusKeyUp = ev => {
    const focusable = focusableMap[ev.target.dataset.trap];

    // We listen for tabbing on keyup otherwise the focus jumps around
    if (ev.key === "Tab") {
      ev.preventDefault;
      if (ev.shiftKey) {
        focusable[focusable.length - 1].focus();
      } else {
        focusable[0].focus();
      }
    }
  };

  const handleTrapFocusKeyDown = ev => {
    /* Prevent default on keydown so focus doesn't escape when you hold tab down */
    ev.preventDefault()
  };

  /* Handler for when nav menu is opened */
  const handleNavMenuOpen = () => {
    navToggle.ariaExpanded = true;
    document.body.style.overflow = "hidden";
  }

  /* Handler for when nav menu is closed */
  const handleNavMenuClose = () => {
    navToggle.ariaExpanded = false;
    document.body.style.overflow = "auto";
  };

  /* Handler for when search menu is opened */
  const handleSearchMenuOpen = () => {
    searchToggle.ariaExpanded = true;
    document.body.style.overflow = "hidden";
    // Set timeout because focus doesn't work until element is visible
    setTimeout(() => {
      /* Autofocus on first focusable element when menu is opened */
      focusableMap.search[0].focus()
    }, 100);
  };

  /* Handler for when search menu is closed */
  const handleSearchMenuClose = () => {
    searchToggle.ariaExpanded = false;
    document.body.style.overflow = "auto";
  };

  /* Bind nav menu toggle handlers */
  navToggle.addEventListener("click", handleNavMenuOpen);
  document.querySelector("#nav-menu-overlay").addEventListener("click", handleNavMenuClose);
  document.querySelector("#nav-menu-close").addEventListener("click", handleNavMenuClose);

  /* Bind search menu toggle handlers */
  searchToggle.addEventListener("click", handleSearchMenuOpen);
  document.querySelector("#search-menu-overlay").addEventListener("click", handleSearchMenuClose);
  document.querySelector("#search-menu-close").addEventListener("click", handleSearchMenuClose);

  /* Bind trap focus handlers */
  document.querySelectorAll(".trap-focus").forEach(el => {
    el.addEventListener("keyup", handleTrapFocusKeyUp)
    el.addEventListener("keydown", handleTrapFocusKeyDown);
  })
});
</script>

<style>
.utility-menu {
    display: flex;
    justify-content: space-between;
    padding: 0  
}

.utility-menu ul {
  overflow: hidden;
  display: block;
  list-style-type: none;
  margin: 0;
  padding: 0;
}
.utility-menu li {
  float: left;
}
.utility-menu li a {
  display: inline-block;
  color: #000;
  float: left;
  text-align: center;
  text-decoration: unset;
#  letter-spacing: 0.72px;
  padding-right: 10px;
}
.utility-menu li a:hover,
.utility-menu li a.is-active, .utility-menu li.active a {
  text-decoration: underline !important;
  text-decoration-color: #be830e !important;
  text-decoration-thickness: 2px !important;
}
</style>

    

<div class="nav-menu" id="nav-menu" role="dialog" aria-labelledby="nav-menu-title">
  <button aria-hidden="true" class="trap-focus" data-trap="nav"></button>

  <nav class="nav-menu__nav">
    <span aria-hidden="true" class="visually-hidden" id="nav-menu-title">Navigation menu</span>

    <a class="nav-menu__brand" href="https://comp.anu.edu.au/courses/comp2310/">
      

<span aria-label="Australian National University logo" class="logo-secondary" role="img"></span>

      
    </a>

    <ul aria-label="Main menu" class="nav-menu__menu container">
      
      
      <span class="visually-hidden">/assessments/01-malloc/, assessments</span>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/">
        Home
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/lectures/">
        Lectures
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/labs/">
        Labs
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/assessments/">
        Assessments
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/resources/">
        Resources
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/problems/">
        Problems
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/people/">
        People
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/policies/">
        Policies
      </a>
      
      </li>
      

      
      
      
      
      <li class="nav-menu__menu-item">
      
      <a class="nav-menu__menu-link" href="https://comp.anu.edu.au/courses/comp2310/help/">
        Help
      </a>
      
      </li>
      
    </ul>

    <a class="nav-menu__close icon-link" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#" id="nav-menu-close" role="button">
      <span class="visually-hidden">Close main menu</span>
      <span aria-hidden="true"><svg class="icon"><use xlink:href="#fas.fa-times"></use></svg></span>
    </a>
  </nav>
  
  <button aria-hidden="true" class="trap-focus" data-trap="nav"></button>  
</div>

<a aria-hidden="true" class="nav-menu-overlay" hidden="" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#" id="nav-menu-overlay" tabindex="-1"></a>

    

<div aria-labelledby="search-menu-title" class="search-menu" id="search-menu" role="dialog">
  <button aria-hidden="true" class="trap-focus" data-trap="search"></button>

  <h3 aria-hidden="true" class="search-menu__title" id="search-menu-title">Search this site</h3>

  

<form action="https://google.com/search" method="get" role="search">
  <div>
    <input type="hidden" name="sitesearch" value="https://comp.anu.edu.au//courses/comp2310">
    <div class="form-control">
      <label class="visually-hidden" for="google-search">Search this site (powered by Google)</label>
      <input class="search-query" id="google-search" name="as_q" placeholder="Type to search" size="16" type="text" value="">
    </div>
    <div class="form-control">
      <input class="search-button" title="Search" type="submit" value="Search">
    </div>
    <p aria-hidden="true" style="text-align: center;">Powered by Google</p>
  </div>
</form>


  <a class="search-menu__close icon-link" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#" id="search-menu-close" role="button">
    <span class="visually-hidden">Close search</span>
    <span aria-hidden="true"><svg class="icon"><use xlink:href="#fas.fa-times"></use></svg></span>
  </a>

  <button aria-hidden="true" class="trap-focus" data-trap="search"></button>
</div>

<a aria-hidden="true" class="search-menu-overlay" hidden="" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#" id="search-menu-overlay" tabindex="-1"></a>

    
      <div class="default">
  
  
  <main aria-label="Main content" class="default" id="main-content">
    
    

<header class="banner banner--medium" style="--background: url(&#39;/courses/comp2310/assets/images/datacenter.jpeg&#39;)">
  <div class="container grid grid--3">
    
    <div class="banner__content">
      
        

<nav aria-label="breadcrumbs" class="breadcrumb">
  <a href="https://comp.anu.edu.au/courses/comp2310/">COMP2310</a> / <a href="https://comp.anu.edu.au/courses/comp2310/assessments/">Assessments</a> / <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/" aria-current="page">Assignment 1: Malloc</a>
</nav>

      
      <h1>Assignment 1: Malloc</h1>
      
        <p class="lead">Implementation of a dynamic memory allocator</p>
      
    </div>
  </div>

  
  
</header>


    <div class="container grid">
      
      
      <aside class="default__page-aside">
        

<section aria-labelledby="toc-section-heading" class="toc-section" role="navigation">
  <a class="visually-hidden" href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#skip-toc-target">Skip table of contents</a>
  <div class="toc-section__heading" id="toc-section-heading">On this page</div>
  

<ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#outline">Outline</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#intro">Introduction</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#background">Background</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#explicit-free-list">Explicit free list</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#dealing-with-memory-fragmentation">Dealing with memory fragmentation</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#placement-policy">Placement policy</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#dealing-with-the-edges-of-chunks">Dealing with the edges of chunks</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#optimizations-cr-d-level">Optimizations (CR-D level)</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#reducing-the-metadata-footprint">Reducing the Metadata Footprint</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#constant-time-coalesce">Constant Time Coalesce</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#multiple-free-lists">Multiple Free Lists</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#getting-additional-chunks-from-the-os">Getting Additional Chunks From the OS</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#performance-measurement">Performance Measurement (CR-level)</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#measuring-execution-time-and-fragmentation">Measuring execution time and fragmentation</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collector-hd-level">Garbage Collector (HD-level)</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#basic-idea">Basic idea</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#modifying-malloc-and-free">Modifying <code class="language-plaintext highlighter-rouge">malloc</code> and <code class="language-plaintext highlighter-rouge">free</code></a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#conservative-gc">Conservative GC</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#lab-specification">Lab Specification</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#malloc-spec">Malloc spec</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#our-implementation-spec">Our Implementation Spec</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#data-structures-and-constants">Data Structures and Constants</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#grade">Marking and Grading Criteria</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#p">P</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#cr">CR</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#d">D</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#hd">HD</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#detailed-specification">Detailed specification</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#allocation">Allocation</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#deallocation">Deallocation</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collection">Garbage collection</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#tasks">Tasks</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#allocation-1">Allocation</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#deallocation-freeing">Deallocation (Freeing)</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#managing-additional-chunks">Managing additional chunks</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collection-1">Garbage Collection</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#performance-analysis">Performance analysis</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#report">Report</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#marking">Marking</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#coding-and-implementation">Coding and Implementation</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mymalloch">mymalloc.h</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mymallocc">mymalloc.c</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#helper-functions">Helper functions</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygch">mygc.h</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygcc">mygc.c</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygctestc">mygctest.c</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testpy">test.py</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#tests">tests/</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchpy">bench.py</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#bench">bench/</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testing">Testing</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#internal-testing">Internal testing</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#address-sanitizer">Address sanitizer</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testing-the-gc">Testing the GC</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking">Benchmarking</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking-execution-time">Benchmarking execution time</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking-fragmentation">Benchmarking fragmentation</a></li></ul></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#submitting-your-work">Submitting your work</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#submission-checklist">Submission checklist</a></li><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#ci-artifacts">Gitlab CI and Artifacts</a><ul><li><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#pdf-artifact">PDF Artifact</a></li></ul></li></ul>

</section>

      </aside>
      

      
      <section class="default__page-content" id="skip-toc-target">
        
<style>
	.info-box, .warn-box, .error-box, .callout-box, .success-box, .think-box, .talk-box, .push-box, .do-box, .extension-box, .hint-box {
		
			padding: 1.5rem;
		
		
			border-left: 4px solid #a8a8a8;
		
	    
			background-color: #e0e0e0;
		
	    
			margin: 1.5rem 0;
		
	}

	
		.info-box {
			border-color: rgb(52, 152, 219);
			background-color: rgba(52, 152, 219, 0.12);
		}

		.info-box::before {
	    	background: #3498db;
	    	color: #fff;
	    	content: "info";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.warn-box {
			border-color: rgb(255, 204, 51);
			background-color: rgba(255, 204, 51, 0.12);
		}

		.warn-box::before {
	    	background: #fc3;
	    	color: #fff;
	    	content: "warn";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.error-box {
			border-color: rgb(255, 0, 0);
			background-color: rgba(255, 0, 0, 0.12);
		}

		.error-box::before {
	    	background: #f00;
	    	color: #fff;
	    	content: "error";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.success-box {
			border-color: rgb(46, 204, 113);
			background-color: rgba(46, 204, 113, 0.12);
		}

		.success-box::before {
	    	background: #2ecc71;
	    	color: #fff;
	    	content: "success";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.think-box {
			border-color: rgb(232, 67, 147);
			background-color: rgba(232, 67, 147, 0.12);
		}

		.think-box::before {
	    	background: #e84393;
	    	color: #fff;
	    	content: "think";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.talk-box {
			border-color: rgb(26, 188, 156);
			background-color: rgba(26, 188, 156, 0.12);
		}

		.talk-box::before {
	    	background: #1abc9c;
	    	color: #fff;
	    	content: "talk";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.push-box {
			border-color: rgb(211, 84, 0);
			background-color: rgba(211, 84, 0, 0.12);
		}

		.push-box::before {
	    	background: #d35400;
	    	color: #fff;
	    	content: "push";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.do-box {
			border-color: rgb(211, 84, 0);
			background-color: rgba(211, 84, 0, 0.12);
		}

		.do-box::before {
	    	background: #d35400;
	    	color: #fff;
	    	content: "do";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.extension-box {
			border-color: rgb(155, 89, 182);
			background-color: rgba(155, 89, 182, 0.12);
		}

		.extension-box::before {
	    	background: #9b59b6;
	    	color: #fff;
	    	content: "extension";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.hint-box {
			border-color: rgb(46, 204, 113);
			background-color: rgba(46, 204, 113, 0.12);
		}

		.hint-box::before {
	    	background: #2ecc71;
	    	color: #fff;
	    	content: "hint";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	
		.-box {
			border-color: rgb();
			background-color: rgba(, 0.12);
		}

		.-box::before {
	    	background: ;
	    	color: #fff;
	    	content: "";
	    	padding-left: 1em;
	    	display: block;
	    	font-weight: 900;
	    	margin-bottom: 1em;
		}
	

</style>

<h2 id="outline">Outline<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#outline" aria-label="Jump to Outline" class="octicon">#</a></h2>

<div class="attention-box">
  <ul>
    <li><strong>Due date:</strong> 13 September 2024, 23:59</li>
    <li><strong>Mark weighting:</strong> 20%</li>
    <li><strong>Submission:</strong> Submit your assignment through <a href="https://gitlab.cecs.anu.edu.au/comp2310/2024/comp2310-2024-assignment-1">GitLab</a>
(<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#getting-started">full instructions below</a>)</li>
    <li><strong>Policies:</strong> For late policies, plagiarism policies, etc., see the <a href="https://comp.anu.edu.au/courses/comp2310/policies/">policies
page</a></li>
  </ul>

  <div class="warn-box">
    <p>This assignment builds upon the following labs:</p>
    <ul>
      <li><a href="https://comp.anu.edu.au/courses/comp2310/labs/05-malloc/">Lab 5: Building Dynamic Memory Allocators</a></li>
      <li><a href="https://comp.anu.edu.au/courses/comp2310/labs/06-malloc-dropin/">Lab 6: Sanity Checking Implicit Free List Implementation</a></li>
    </ul>
  </div>

  <p>If you have not completed the tasks in the above labs or do not understand the
content, we <em>strongly</em> recommend that you first complete the labs and then
start the assignment.</p>

  <h2 id="intro">Introduction<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#intro" aria-label="Jump to Introduction" class="octicon">#</a></h2>

  <p>Managing memory is a major part of programming in C. You have used <code class="language-plaintext highlighter-rouge">malloc()</code> and <code class="language-plaintext highlighter-rouge">free()</code> in the recent labs. You have also built a very basic memory allocator, and it is now time to build a more advanced allocator.
In this assignment, you will implement a memory allocator, which allows users to malloc() and free() memory as needed.
Your allocator will request large chunks of memory from the OS and efficiently manage all the bookkeeping and memory.
The allocator we ask you to implement is inspired by the DLMalloc allocator designed by Doug Lea. The DLMalloc allocator also inspired the PTMalloc allocator, which GLibC currently uses. Indeed, our allocator is a simplified version of DLMalloc, but you will also notice many similarities.</p>

  <h2 id="background">Background<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#background" aria-label="Jump to Background" class="octicon">#</a></h2>

  <p>We hope that the last two labs have motivated the need for dynamic memory allocators. Specifically, we have seen that while it is certainly possible to use the low-level <code class="language-plaintext highlighter-rouge">mmap</code> and <code class="language-plaintext highlighter-rouge">munmap</code> functions to manage areas of virtual memory, programmers need the convenience and efficiency of more fine-grained memory allocators. If we managed the memory from the OS ourselves, we could allow allocating and freeing variables in any order, and also reuse memory for other variables.</p>

  <p>The last lab taught you how best to build an implicit free list allocator for managing free blocks. In this assignment, we will first build a more efficient free list data structure called an explicit free list. We will also change our placement policy to <strong>best fit</strong>, and then perform a number of optimizations.</p>

  <h3 id="explicit-free-list">Explicit free list<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#explicit-free-list" aria-label="Jump to Explicit free list" class="octicon">#</a></h3>

  <p>The block allocation time with an implicit free list is linear in the total number of heap blocks which is not suitable for a high-performance allocator. We can add a <em>next</em> and <em>previous</em> pointer to each block’s metadata so that we can iterate over the unallocated blocks. The resulting linked list data structure is called an explicit free list.
Using a doubly linked list instead of a free list reduces the allocation time from linear in the total number of blocks to linear in the total number of free blocks.</p>

  <h3 id="dealing-with-memory-fragmentation">Dealing with memory fragmentation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#dealing-with-memory-fragmentation" aria-label="Jump to Dealing with memory fragmentation" class="octicon">#</a></h3>

  <p>Fragmentation occurs when otherwise unused memory is not available to satisfy allocate requests. This phenomenon happens because when we split up large blocks into smaller ones to fulfill user requests for memory, we end up with many small blocks. However, some of those blocks may be able to be merged back into a larger block. To address this issue requires us to iterate over the free list and make an effort to find if the block we are trying to free is adjacent to another already free block. If neighboring blocks are free, we can coalesce them into a single larger block.</p>

  <h3 id="placement-policy">Placement policy<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#placement-policy" aria-label="Jump to Placement policy" class="octicon">#</a></h3>

  <p>Memory fragmentation is also affected by <strong>placement policy</strong>, which is how you choose a block to allocate when given a choice between multiple free blocks which are suitable (large enough). The policy we used in Lab 5 was the <strong>first fit</strong> policy, returning the first free block we find. There are a number of alternative strategies with the aim of targeting fragmentation, sometimes with a tradeoff of performance:</p>
  <ul>
    <li><strong>Best fit</strong>, returning the <em>smallest</em> suitable free block (leaves bigger free blocks available).</li>
    <li><strong>Next fit</strong>, which starts looking for a free block from where the previous allocation was (addresses issues with First Fit such as a tendency to allocate memory at the beginning of the chunk and create more fragments there)</li>
  </ul>

  <p>The base spec of this assignment requires you to implement <strong>best fit</strong>. Note that in the most naive explicit free list implementation, this does come at the performance cost of looking through the <em>entire</em> free list! But one of the optimisations we describe below will heavily mitigate this. You may also consider your own ideas for mitigating this cost.</p>

  <h3 id="dealing-with-the-edges-of-chunks">Dealing with the edges of chunks<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#dealing-with-the-edges-of-chunks" aria-label="Jump to Dealing with the edges of chunks" class="octicon">#</a></h3>

  <p>One detail we must consider is how to handle the edges of the chunks from the OS. If we simply start the first allocable block at the beginning of the memory chunk, then we may run into problems when trying to free the block later. This is because a block at the edge of the chunk is missing a neighbor.
A simple solution to this is to insert a pair of fenceposts at either end of the chunk. The fencepost is a dummy header containing no allocable memory, but which serves as a neighbor to the first and last allocable blocks in the chunk. Now we can look up the neighbors of those blocks and don’t have to worry about accidentally coalescing outside of the memory chunk allocated by the OS, because anytime one of the neighbors is a fencepost we cannot coalesce in that direction.</p>

  <h2 id="optimizations-cr-d-level">Optimizations (CR-D level)<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#optimizations-cr-d-level" aria-label="Jump to Optimizations (CR-D level)" class="octicon">#</a></h2>

  <p>We will also perform the following optimizations as part of the assignment to improve the space and time complexity of our memory allocator.</p>

  <h3 id="reducing-the-metadata-footprint">Reducing the Metadata Footprint<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#reducing-the-metadata-footprint" aria-label="Jump to Reducing the Metadata Footprint" class="octicon">#</a></h3>

  <ul>
    <li>
      <p><strong>Naive solution:</strong> In our description of the explicit free list above, we assume the memory allocated to the user begins after all of the block’s metadata. We must maintain the metadata like size and allocation status because we need it in the block’s header when we free the object.</p>
    </li>
    <li>
      <p><strong>Optimization 1:</strong> While we need to maintain the size and allocation status, we only use the free list pointers when the object is free. If the object has been allocated, it is no longer in a free list; thus, the memory used to store the pointers can be used for other purposes. By placing the next and previous pointers at the end of the metadata, we can save an additional 2 * sizeof(pointer) bytes and add that to the memory allocated to the user.</p>
    </li>
    <li>
      <p><strong>Optimization 2:</strong> The allocated flag that tells if a block is allocated or not uses only one bit. Since the sizes are rounded up to the next 8 bytes, the last three bits are not used. Instead of using a boolean to store the allocated flag, we can use one of the unused bits in size. That will save an additional 8 bytes.</p>
    </li>
  </ul>

  <h3 id="constant-time-coalesce">Constant Time Coalesce<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#constant-time-coalesce" aria-label="Jump to Constant Time Coalesce" class="octicon">#</a></h3>

  <ul>
    <li>
      <p><strong>Naive solution:</strong> We mentioned above that we could iterate over the free list to find blocks that are next to each other, but unfortunately, that makes the free operation O(n), where n is the number of blocks in the list.</p>
    </li>
    <li>
      <p><strong>Optimized solution:</strong> The solution we will use is to add another data structure called Boundary Tags, which allows us to calculate the location of the right and left blocks in memory. To calculate the location of the block to the right, all we need to know is the size of the current block. To calculate the location of the block to the left, we must also maintain the size of the block to the left in each block’s metadata. Now we can find the neighboring blocks in O(1) time instead of O(n).</p>
    </li>
  </ul>

  <h3 id="multiple-free-lists">Multiple Free Lists<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#multiple-free-lists" aria-label="Jump to Multiple Free Lists" class="octicon">#</a></h3>

  <ul>
    <li>
      <p><strong>Naive solution:</strong> So far, we have assumed a single free list containing all free blocks. To find a block large enough to satisfy a request, we must iterate over all the blocks to find a block large enough to fulfil the request. For best fit, we also need to look through ALL of the free blocks to find the best such block.</p>
    </li>
    <li>
      <p><strong>Optimized solution:</strong> We can use multiple free lists. We create <code class="language-plaintext highlighter-rouge">n</code> free lists<sup id="fnref:1" role="doc-noteref"><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#fn:1" class="footnote" rel="footnote">1</a></sup>, one for each allocation size (8, 16, …, 8*(n-1), 8*n bytes.) That way, when a user requests memory, we can jump directly to the list representing blocks that are the correct size instead of looking through a general list. If that list is empty, the next non-empty list will contain the block best fitting the allocation request. However, we only have <code class="language-plaintext highlighter-rouge">n</code> lists, so if the user requests <code class="language-plaintext highlighter-rouge">8*n</code> bytes of memory or more, we fall back to the naive approach and scan the final list for blocks that can satisfy the request. This optimization cannot guarantee an O(1) allocation time for all allocations. Still, for any allocation under 8*n, the allocation time is O(number of free lists) as opposed to O(length of the free list).</p>
    </li>
  </ul>

  <h3 id="getting-additional-chunks-from-the-os">Getting Additional Chunks From the OS<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#getting-additional-chunks-from-the-os" aria-label="Jump to Getting Additional Chunks From the OS" class="octicon">#</a></h3>

  <p>The allocator may be unable to find a fit for the requested block. If the free blocks are already maximally coalesced, then the allocator asks the kernel for additional heap memory by calling <code class="language-plaintext highlighter-rouge">mmap</code>. The allocator transforms the additional memory into one large free block, inserts the block in the free list, and then places the requested block in this new free block.</p>

  <p>Note that for the purposes of performance analysis and calculating fragmentation (<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#performance-measurement">see below</a>), and for determining invalid pointers passed to free due to them not lying in any allocated chunk, you will need to implement a way to iterate through all of the chunks and keep track of where they all are. Hint: consider using a linked list and extra fields in the chunk fenceposts.</p>

  <h2 id="performance-measurement">Performance Measurement (CR-level)<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#performance-measurement" aria-label="Jump to Performance Measurement (CR-level)" class="octicon">#</a></h2>

  <p>Given the effort that we are going to in order to optimise the performance of our allocator, we would like to know that it is actually having an effect! There are two primary metrics for the performance of the allocator:</p>
  <ul>
    <li>Execution time: The raw best/average/worst time it takes to perform an allocation, and to free.</li>
    <li>Fragmentation: Measuring the allocator’s ability to efficiently use memory. Divided into two classes: internal fragmentation, created by space inside blocks which is unusable (e.g. extra padding to meet alignment constraints or metadata), and external fragmentation, caused by space being divided up too much and there being small “fragments” in between allocated blocks which cannot satisfy most requests and sit there wasting space.</li>
  </ul>

  <p>It is worth noting that these metrics will change based on these inputs:</p>
  <ul>
    <li>Number of allocations made so far/how long the program has been running</li>
    <li>Allocation and freeing patterns</li>
  </ul>

  <p>As you add optimisations and improve your allocator, you should compare your new iterations’ performance to your old one. This will involve keeping different versions of your allocator allowed in different files (we will advise how to run tests on the allocator given in a specific file in the <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testing">testing</a> section). You are required to at least analyse the performance benefit arising from your “best” optimisation, e.g. multiple free lists, by comparing a version of the allocator with and without it. You will be asked to analyse this in your report.</p>

  <p>Note that if you don’t keep any prior versions, this is also fine, you will just have to make a baseline allocator to compare against (by copying the current allocator to a new file and undoing your best optimisation) yourself.</p>

  <h3 id="measuring-execution-time-and-fragmentation">Measuring execution time and fragmentation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#measuring-execution-time-and-fragmentation" aria-label="Jump to Measuring execution time and fragmentation" class="octicon">#</a></h3>

  <p>Measuring execution time is straightforward using the Linux <code class="language-plaintext highlighter-rouge">time</code> command on a program which is making some number of allocations.</p>

  <p>Measuring fragmentation is more tricky. The lectures describe a metric called peak memory utilisation which you can use for this; see Slides 12-14 in <a href="https://comp.anu.edu.au/courses/comp2310/assets/lectures/week6-malloc-basic.pdf">the “malloc-basic” half of Week 6’s lectures</a> for details. This will require you to sum up the payload sizes across all blocks, which requires iterating through all of the blocks (in each chunk) in the first place; we will have you define helper functions for doing this. You can also develop your own metrics for measuring fragmentation if you wish.</p>

  <p>We will provide you benchmarking programs on which you can measure these metrics and see how they scale with number of allocations. See the <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking">benchmarking section</a> for more.</p>

  <h2 id="garbage-collector-hd-level">Garbage Collector (HD-level)<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collector-hd-level" aria-label="Jump to Garbage Collector (HD-level)" class="octicon">#</a></h2>

  <p>A critical pitfall of the <code class="language-plaintext highlighter-rouge">malloc</code>/<code class="language-plaintext highlighter-rouge">free</code> manual style of memory management is that if the user forgets to free memory, it results in a memory leak, i.e., memory is consumed even if the block is no longer used or not even reachable by the program. The garbage collector (GC) is an alternative to manual freeing that takes this burden off the user by automatically figuring out if allocations are still being used, and freeing those which are not (i.e., dead memory). You will implement what is called a “conservative mark-and-sweep GC” in this assignment.</p>

  <h3 id="basic-idea">Basic idea<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#basic-idea" aria-label="Jump to Basic idea" class="octicon">#</a></h3>

  <p>The basic idea is simple. The program has a bunch of variables which it can access directly by name which we call the <strong>roots</strong>. The roots consist of local variables as well as global variables (though for simplicity we will ignore the latter for this assignment). These roots can then be pointers to objects on the heap, which may themselves be pointers, and so on. Any object which cannot be reached by a series of pointer dereferences starting from the roots is <strong>unreachable</strong> and hence garbage, and can safely be deallocated. Meanwhile, if an object IS reachable, then it may still be used later in the program and we cannot free its memory.</p>

  <p>Our GC will be a function that frees all blocks that do not contain any reachable objects. The GC consists of two phases: <em>mark</em> and <em>sweep</em>. In the mark phase, we start from the roots and look for pointers to locations on the heap. If we find a pointer that points to a location within a block on the heap, we “mark” that block as reachable by changing a flag in the header (similar to the allocated flag). Once done, we then go through and free all of the allocated blocks that were not marked in the “sweep” phase.</p>

  <p>The mark flag can be implemented as one of the unused bits at the end of the size parameter in your header.</p>

  <h3 id="modifying-malloc-and-free">Modifying <code class="language-plaintext highlighter-rouge">malloc</code> and <code class="language-plaintext highlighter-rouge">free</code><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#modifying-malloc-and-free" aria-label="Jump to Modifying malloc and free" class="octicon">#</a></h3>

  <p>Your malloc and free will need to be modified a bit so that they maintain a data structure tracking the allocated blocks and the locations of their headers. The reasons are twofold:</p>
  <ul>
    <li>In the mark phase, if you have a pointer to the middle of a block, you will need to then find the header of the block in order to set the mark flag. This can be done by going through all the allocated block headers and choosing the one corresponding to the block containing the pointer’s location.</li>
    <li>In the sweep phase, you need to go through each of the allocated blocks when freeing the unmarked ones.</li>
  </ul>

  <p>One way is to keep next/prev pointers in the headers of allocated blocks and having your malloc/free maintain a “used list”, similar to the free lists you’ve used so far. Of course, this uses extra metadata, and you need to go through all of the allocated blocks just to find the header of a single one. You are encouraged to use a better approach if you can think of one.</p>

  <h3 id="conservative-gc">Conservative GC<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#conservative-gc" aria-label="Jump to Conservative GC" class="octicon">#</a></h3>

  <p>Now, the idea of an “object” in C is quite loose, and there are two problems:</p>
  <ul>
    <li>Any value can be cast to a pointer and dereferenced. So even if a variable is of type <code class="language-plaintext highlighter-rouge">int</code>, it has to be treated as a pointer.</li>
    <li>A pointer points to a single location in memory, but using pointer offsets we could also access nearby locations. E.g. if the pointer points to an array we’d access the elements of that array via offsets. Given a pointer, you can’t tell where the object pointed to begins and ends.</li>
  </ul>

  <p>This is why we will make our allocator “conservative”, which means that it may fail to free some blocks which are actually garbage, but it will <em>never free a block which may be used</em>. In practice:</p>
  <ul>
    <li>When checking the local variables/roots for pointers we scan the entire stack, casting all word-aligned values to pointers (as any of them may be interpreted as pointers).</li>
    <li>When a pointer to a block is found, we don’t just check the value being pointed to but all other word-aligned values in that block for further pointers (as those values can be accessed by offsets from the original pointer).</li>
  </ul>

  <p class="info-box">In order to have a more “precise” GC, you need more support from the programming language and the compiler to provide 
constraints on what objects can be and how you define them, which allows things like having metadata inside the objects themselves so that we can mark individual objects rather than blocks. GCs in practice tend to be built into the programming language itself, such as in Java. You may learn more about this if you take a compiler course in future.</p>

  <h2 id="lab-specification">Lab Specification<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#lab-specification" aria-label="Jump to Lab Specification" class="octicon">#</a></h2>

  <h3 id="malloc-spec">Malloc spec<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#malloc-spec" aria-label="Jump to Malloc spec" class="octicon">#</a></h3>

  <p>You can read the malloc interface on the malloc man page. Many details are left up to the library’s authors. For instance, consider the many optimizations we mention above. All versions of malloc would be correct by the specification on the man page, but some are more efficient than others.</p>

  <p>We will also require you to define a set of malloc helper functions. The reasons for these are two-fold:</p>
  <ul>
    <li>The helper functions can be used to implement “internal” tests that allow writing unit tests for sub-parts of the malloc. The helper functions also allow probing the “free space” currently available to malloc and assessing fragmentation without knowing the internal implementation details. This will be used in both tests and benchmarking.</li>
    <li>Splitting up code into helper functions is good style, and you will find many of these helper functions useful for modularising your code.</li>
  </ul>

  <h3 id="our-implementation-spec">Our Implementation Spec<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#our-implementation-spec" aria-label="Jump to Our Implementation Spec" class="octicon">#</a></h3>

  <p>The major elements of the base spec of our malloc are as follows:</p>
  <ul>
    <li>Use an explicit free list</li>
    <li>Use the best fit placement policy</li>
  </ul>

  <p>We will also implement special behavior for <code class="language-plaintext highlighter-rouge">my_free</code> to do no-op in cases where the pointer being freed is <em>obviously</em> invalid, i.e. does not correspond to a malloc call. We don’t require handling all such cases, e.g. pointers into the middle of blocks, but the following cases should be handled gracefully:</p>
  <ul>
    <li><code class="language-plaintext highlighter-rouge">free</code> is called when the memory allocator has not been initialised</li>
    <li><code class="language-plaintext highlighter-rouge">free</code> is called with a pointer which is not in the range of any of the chunks mmapped by the allocator</li>
  </ul>

  <p>We have described the basic implementation we want you to follow with optimizations in the background and optimization sections above. We now provide the technical specification of the required design. Some of the requirements are in place to enforce conformance to the design, and others guarantee determinism between our reference allocator and your allocator for testing. The specification below should contain all the details necessary to ensure your implementation is consistent with the reference implementation.</p>

  <h3 id="data-structures-and-constants">Data Structures and Constants<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#data-structures-and-constants" aria-label="Jump to Data Structures and Constants" class="octicon">#</a></h3>

  <p>We provide certain constants, namely:</p>

  <ol>
    <li><code class="language-plaintext highlighter-rouge">kMemorySize</code>: When requesting a chunk of memory from the OS for allocation, 
we always get a multiple of 64MB. For objects larger than 64 MB, you will 
have to use a multiple of 64 MB.</li>
    <li><code class="language-plaintext highlighter-rouge">kAlignment</code>: We require word-aligned addresses from our allocations.</li>
    <li><code class="language-plaintext highlighter-rouge">kMinAllocationSize</code>: We initially set the minimum allocation size for our allocator to be 1 word.
You are allowed to change this to accommodate the metadata reduction optimisations.</li>
    <li><code class="language-plaintext highlighter-rouge">kMaxAllocationSize</code>: We set the maximum allocation size for our allocator 
to be 128 MB - size of your meta-data. Note that this is the maximum 
allocation size an <em>individual</em> request to <code class="language-plaintext highlighter-rouge">my_malloc</code>. It is possible for
the total size across all allocations to be greater than <code class="language-plaintext highlighter-rouge">kMaxAllocationSize</code>.</li>
    <li><code class="language-plaintext highlighter-rouge">N_LISTS</code>: We set the number of free lists in to be <code class="language-plaintext highlighter-rouge">59</code>. This is only 
relevant when implementing the “<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#multiple-free-lists">Multiple Free Lists</a>” 
optimisation. You are allowed and encouraged to change this while debugging/testing performance
to see its impact on your allocator.</li>
  </ol>

  <h2 id="grade">Marking and Grading Criteria<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#grade" aria-label="Jump to Marking and Grading Criteria" class="octicon">#</a></h2>

  <p>You are required to submit a completed and working implementation of <code class="language-plaintext highlighter-rouge">malloc</code> according to this spec, as well as a <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#report">report</a> discussing your implementation. The marks will be split in the following way:</p>
  <ul>
    <li>Code (60%)</li>
    <li>Report, including performance analysis (40%)</li>
  </ul>

  <p>The following description of grading categories assumes you submit both the code for your malloc implementation and the report.</p>

  <div class="warn-box">
    <p>Keep in mind that just <em>attempting</em> the given tasks for a grade band is not enough to <em>guarantee</em> you receive a final mark in that grade band. Things like correctness of your implementation, report quality and code style will all influence your results. This is just provided as a guideline.</p>
  </div>

  <h3 id="p">P<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#p" aria-label="Jump to P" class="octicon">#</a></h3>

  <p>You will be rewarded a maximum grade of <code class="language-plaintext highlighter-rouge">P</code> if you complete the following tasks.</p>
  <ul>
    <li>Implement a single explicit free list with <strong>best fit</strong> placement policy</li>
    <li>Linear time coalescing</li>
    <li>Fence posts</li>
  </ul>

  <div class="hint-box">
    <p>To be able to fulfil <code class="language-plaintext highlighter-rouge">kMaxAllocationSize</code> requests after you have implemented 
  fence posts, you can either:</p>

    <ul>
      <li>Modify the <code class="language-plaintext highlighter-rouge">kMaxAllocationSize</code> constant to subtract the size taken up by 
the fence posts.</li>
      <li>Modify your code to calculate how many multiples of <code class="language-plaintext highlighter-rouge">64MB</code> the call to <code class="language-plaintext highlighter-rouge">mmap</code>
should request, so that it takes the size of the fenceposts into 
consideration.</li>
    </ul>
  </div>

  <h3 id="cr">CR<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#cr" aria-label="Jump to CR" class="octicon">#</a></h3>

  <p>You will be rewarded a maximum grade of <code class="language-plaintext highlighter-rouge">CR</code> if you complete the following tasks.</p>
  <ul>
    <li>All tasks in the <code class="language-plaintext highlighter-rouge">P</code> category</li>
    <li>Metadata reduction</li>
    <li>Constant time coalescing with boundary tags</li>
    <li>Requesting additional chunks from the OS</li>
    <li>Performance analysis on the effect of the extensions in this category</li>
  </ul>

  <h3 id="d">D<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#d" aria-label="Jump to D" class="octicon">#</a></h3>

  <p>You will be rewarded a maximum grade of <code class="language-plaintext highlighter-rouge">D</code> if you complete the following tasks.</p>
  <ul>
    <li>All tasks in the <code class="language-plaintext highlighter-rouge">P</code> and <code class="language-plaintext highlighter-rouge">CR</code> categories</li>
    <li>Multiple free lists</li>
    <li>Performance analysis on the effect of the extensions in this category</li>
  </ul>

  <h3 id="hd">HD<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#hd" aria-label="Jump to HD" class="octicon">#</a></h3>

  <p>You will be rewarded a maximum grade of <code class="language-plaintext highlighter-rouge">HD</code> if you complete the following tasks.</p>
  <ul>
    <li>All tasks in the <code class="language-plaintext highlighter-rouge">P</code>, <code class="language-plaintext highlighter-rouge">CR</code> and <code class="language-plaintext highlighter-rouge">D</code> categories</li>
    <li>The garbage collector</li>
  </ul>

  <h2 id="detailed-specification">Detailed specification<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#detailed-specification" aria-label="Jump to Detailed specification" class="octicon">#</a></h2>

  <p>Here, we elaborate further on the exact specification for each task.</p>

  <h3 id="allocation">Allocation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#allocation" aria-label="Jump to Allocation" class="octicon">#</a></h3>

  <ul>
    <li>An allocation of 0 bytes should return the <code class="language-plaintext highlighter-rouge">NULL</code> pointer for determinism.</li>
    <li>All chunks requested from the OS should be a multiple of size <code class="language-plaintext highlighter-rouge">kMemorySize</code> defined in mymalloc.h.</li>
    <li>All requests from the user are rounded up to the nearest multiple of <code class="language-plaintext highlighter-rouge">kAlignment</code> (8 bytes).</li>
    <li>The minimum request size is the size of the full header struct. Even though the pointer fields at the end of the header are not used when the block is allocated, they are necessary when the block is free, and if space is not reserved for them, it could lead to memory corruption when freeing the block.</li>
    <li>When allocating from the final free list (<code class="language-plaintext highlighter-rouge">N_LISTS - 1</code>), the blocks are allocated in best-fit order: you will iterate the list and look for the smallest block large enough to satisfy the request size. Given that all other lists are multiples of 8, and all blocks in each list are the same size, this is not an issue with the other lists.</li>
    <li>When allocating a block, there are a few cases to consider:
      <ul>
        <li>If the block is exactly the request size, the block is simply removed from the free list.</li>
        <li>If the block is larger than the request size, but the remainder is too small to be allocated on its own, the extra memory is included in the memory allocated to the user and the full block is still allocated just as if it had been exactly the right size.</li>
        <li>If the block is larger than the request size and the remainder is large enough to be allocated on its own, the block is split into two smaller blocks. We could allocate either of the blocks to the user, but for determinism, the user is allocated the block which is higher in memory (the rightmost block).</li>
        <li>When splitting a block, if the size of the remaining block is no longer appropriate for the current list, the remainder block should be removed and inserted into the appropriate free list.</li>
      </ul>
    </li>
    <li>When no available block can satisfy the user’s request, we must request another chunk of memory from the OS and retry the allocation. On initialization of the library, the allocator obtains a chunk from the OS and inserts it into the free list. The pointer to the new chunk should be saved somewhere in a way that allows traversing across all of the chunks in some order.</li>
    <li>In operating systems, you can never expect a call to the OS to work all the time. If allocating a new chunk from the OS fails, your code should return the NULL pointer, and <code class="language-plaintext highlighter-rouge">errno</code> should be set appropriately (check the man page).</li>
    <li>The allocator should allocate new chunks lazily. Specifically, the allocator requests more memory only when servicing a request that cannot be satisfied by any available free blocks.</li>
  </ul>

  <h3 id="deallocation">Deallocation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#deallocation" aria-label="Jump to Deallocation" class="octicon">#</a></h3>

  <ul>
    <li>Freeing a NULL pointer is a no-op (don’t do anything).</li>
    <li>When freeing a block, you need to consider a few cases:
      <ul>
        <li>Neither the right nor the left blocks are unallocated. In this case, simply insert the block into the appropriate free list</li>
        <li>Only the right block is unallocated. Then coalesce the current and right blocks together. The newly coalesced block should remain where the right block was in the free list</li>
        <li>Only the left block is unallocated. Then coalesce the current and left blocks, and the newly coalesced block should remain where the left block was in the free list.</li>
        <li>Both the right and left blocks are unallocated, and we must coalesce with both neighbors. In this case, the coalesced block should remain where the left block (lower in memory) was in the free list.</li>
      </ul>
    </li>
    <li>When coalescing a block, if the size of the coalesced block is no longer appropriate for the current list, the newly formed block should be removed and inserted into the appropriate free list. (Note: This applies even to cases above where it is mentioned to leave the block where it was in the free list.)</li>
    <li><code class="language-plaintext highlighter-rouge">my_free</code> should behave gracefully (i.e. not crash) when given obviously invalid memory addresses. For the purposes of this requirement an invalid memory address is one which is not in the range of any of the chunks mmapped by the <code class="language-plaintext highlighter-rouge">my_malloc</code>.</li>
  </ul>

  <h3 id="garbage-collection">Garbage collection<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collection" aria-label="Jump to Garbage collection" class="octicon">#</a></h3>

  <ul>
    <li>Garbage collector uses a modified version of <code class="language-plaintext highlighter-rouge">malloc</code> that creates a “used list” or other data structure to track
allocated blocks, potentially using extra metadata in blocks to do so. Your <code class="language-plaintext highlighter-rouge">free</code> will also need to remove blocks from this data structure.</li>
    <li>Garbage collection is a function that can be called by the program anytime, like “free” except you don’t need
to tell it what to free (it will figure it out by itself)</li>
    <li>GC’s mark phase scans the entire stack and considers any word-aligned value in the stack as a pointer</li>
    <li>You are already provided a function <code class="language-plaintext highlighter-rouge">get_end_of_stack()</code> that returns a pointer to the end of the stack, and there is also a global variable <code class="language-plaintext highlighter-rouge">start_of_stack</code> which you can assume has been pre-initialised to the start of <code class="language-plaintext highlighter-rouge">main()</code>’s stack frame. The use of these two is demonstrated in the template file for GC that you’re provided.</li>
    <li>GC ignores global variables and variables stored in registers</li>
    <li>If a pointer to a block is found, the entire block is scanned for further pointers</li>
    <li>GC is resistant to circular references and mark phase does not re-scan a block that it’s already scanned. E.g. if
block 1 contains a pointer to block 2, which contains a pointer back to block 1, your mark phase must not fall into
an infinite loop.</li>
    <li>When sweeping/freeing unused blocks, garbage blocks are removed from the used list (or analogous data structure) and added to the appropriate free lists, and the same rules for coalescing described for <code class="language-plaintext highlighter-rouge">free</code> are applied.</li>
  </ul>

  <h2 id="tasks">Tasks<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#tasks" aria-label="Jump to Tasks" class="octicon">#</a></h2>

  <p>Your task is to implement <code class="language-plaintext highlighter-rouge">malloc</code> (memory allocator) and include in your implementation the various requirements and optimizations discussed above. Broadly, your coding tasks are three-fold.</p>

  <h3 id="allocation-1">Allocation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#allocation-1" aria-label="Jump to Allocation" class="octicon">#</a></h3>

  <ol>
    <li>Calculate the required block size.</li>
    <li>Find the appropriate free list to look for a block to allocate.</li>
    <li>Depending on the size of the block, either allocate the full block or split the block and allocate the right (higher in memory) portion to the user.</li>
    <li>When allocating a block, update its allocation status.</li>
    <li>Finally, return the user a pointer to the data field of the header.</li>
  </ol>

  <h3 id="deallocation-freeing">Deallocation (Freeing)<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#deallocation-freeing" aria-label="Jump to Deallocation (Freeing)" class="octicon">#</a></h3>

  <ol>
    <li>Free is called on the same pointer that <code class="language-plaintext highlighter-rouge">malloc</code> returned, which means we must calculate the location of the header by pointer arithmetic.
<em>Hint</em>: You will most likely want to use the <code class="language-plaintext highlighter-rouge">ptr_to_block</code> helper function for this.</li>
    <li>Once we have the block’s header freed, we must calculate the locations of its right and left neighbors, using pointer arithmetic and the block’s size fields.</li>
    <li>Based on the allocation status of the neighboring blocks, we must either insert the block or coalesce it with one or both of the neighboring blocks.</li>
  </ol>

  <h3 id="managing-additional-chunks">Managing additional chunks<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#managing-additional-chunks" aria-label="Jump to Managing additional chunks" class="octicon">#</a></h3>

  <p>Handle the case where the user’s request cannot be fulfilled by any of the available blocks. Also implement a method for traversing across all of the chunks currently used by the allocator, for use in calculating fragmentation and detecting
invalid frees.</p>

  <div class="warn-box">
    <p>Note that the tests we provide will succeed even if you submit an <code class="language-plaintext highlighter-rouge">mmap</code> or an implicit free list allocator. The success of these provided tests on a non-explicit free list allocator does not mean you are done. Do not submit code files with allocators from a previous lab. We have tests to ensure compliance with the assignment specification.</p>
  </div>

  <h3 id="garbage-collection-1">Garbage Collection<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#garbage-collection-1" aria-label="Jump to Garbage Collection" class="octicon">#</a></h3>

  <ol>
    <li>Modify malloc and free to maintain additional data structures your GC needs</li>
    <li>Iterate from the beginning to the end of the stack. For each value in the stack, find if that value is an address
to a location inside an allocated block. If such a block is found, set its mark flag.</li>
    <li>Recursively scan each block marked in step 2 for pointers to further blocks until no more blocks can be marked.</li>
    <li>Go through all allocated blocks and call <code class="language-plaintext highlighter-rouge">free</code> for any remaining unmarked blocks.</li>
  </ol>

  <h3 id="performance-analysis">Performance analysis<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#performance-analysis" aria-label="Jump to Performance analysis" class="octicon">#</a></h3>

  <ol>
    <li>Implement at least the peak memory utilisation metric for fragmentation.</li>
    <li>Measure and compare execution time and fragmentation for various levels of optimisation of your allocator, and for various input sizes. At least comparing your “best” allocator with a “second best” (a version missing the best optimisation you implemented)</li>
  </ol>

  <h3 id="report">Report<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#report" aria-label="Jump to Report" class="octicon">#</a></h3>

  <p>You <em>must</em> submit a report that describes your malloc implementation. It should 
be written in the given <code class="language-plaintext highlighter-rouge">report.md</code> file as valid markdown and split up into the
following sections. Some of these will be omitted if you did not complete those
specific optimisations:</p>

  <ul>
    <li><strong>Overview</strong> of your memory allocator, and the data structures used. (<em>100-300 words</em>)
      <ul>
        <li>You should make it clear what optimisations you have attempted in this 
Overview section, but leave the important details until the relevant optimisation
section.</li>
        <li>You should include a high level explanation of how your best fit allocation
strategy operates, how coalescing is implemented, and how fenceposts were
implemented.</li>
      </ul>
    </li>
    <li><strong>Optimisations</strong>: for each of the following optimisations you attempt, include 
a section going into more detail about how you implemented it and what effect
(if any) it had on your memory allocator:
      <ul>
        <li>Metadata Reduction (<em>50-100 words</em>)</li>
        <li>Constant time coalescing with boundary tags (<em>50-150 words</em>)</li>
        <li>Requesting additional chunks from the OS (<em>50-150 words</em>)</li>
        <li>Multiple Free Lists (<em>50-200 words</em>)</li>
      </ul>
    </li>
    <li><strong>Garbage Collector Overview</strong>: (<em>100-500 words</em>)
      <ul>
        <li>If you implemented the garbage collector provide an overview of how your 
garbage collector works and the changes you made to the metadata stored.</li>
        <li>Describe any problems with implementing a garbage collector in C, and why 
garbage collectors in general require more support from the programming 
language itself.</li>
      </ul>
    </li>
    <li><strong>Testing</strong>: (<em>100-300 words</em>)
      <ul>
        <li>You should include at least one of the following:
          <ul>
            <li>Explanation of an implementation challenge encountered in completing this 
assignment. This could include a difficult bug you faced or a conceptual
problem you got stuck on.</li>
            <li>Explanation of additional tests you created to verify your malloc 
and/or garbage collector implementation</li>
            <li>If there are any known bugs in your implementation, list them here in this
section.</li>
          </ul>
        </li>
      </ul>
    </li>
    <li><strong>Benchmarking Results</strong>: (<em>100-300 words</em>)
      <ul>
        <li>Include a summary of your memory allocators performance under the benchmark
script. Identify any optimisations you performed that improved the results 
significantly.</li>
        <li>Include any measurements of memory fragmentation you computed.</li>
      </ul>
    </li>
  </ul>

  <div class="warn-box">
    <p>The report job of the <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#ci-artifacts">CI</a> will fail if you exceed 1200 words.
  If your report is still within the word count indicated above (2000 words), 
  you are allowed to safely ignore this failure.</p>
  </div>

  <h3 id="marking">Marking<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#marking" aria-label="Jump to Marking" class="octicon">#</a></h3>

  <p>The code is worth 60% of your grade (in your specific <a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#grade">category</a>). The report is worth 40% of the grade.</p>

  <p>Note that having appropriate code style will contribute a small amount to your code mark. This means you should:</p>

  <ul>
    <li>Have clear names for functions and variables</li>
    <li>Have comments explaining what more complex functions do</li>
    <li>Remove any commented out code before submission</li>
    <li>Remove excessive whitespace</li>
    <li>Have <em>consistent</em> whitespace</li>
    <li>Make sure you only use the <code class="language-plaintext highlighter-rouge">LOG</code> macro to print things to stdout/stderr, so 
these are automatically removed when a release build is used.</li>
  </ul>

  <h2 id="coding-and-implementation">Coding and Implementation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#coding-and-implementation" aria-label="Jump to Coding and Implementation" class="octicon">#</a></h2>

  <p>Fork the <a href="https://gitlab.cecs.anu.edu.au/comp2310/2024/comp2310-2024-assignment-1">Assignment 1 repo</a> and then clone it locally.</p>

  <h3 id="mymalloch">mymalloc.h<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mymalloch" aria-label="Jump to mymalloc.h" class="octicon">#</a></h3>

  <p>This file contains the type signatures of <code class="language-plaintext highlighter-rouge">my_malloc</code> and <code class="language-plaintext highlighter-rouge">my_free</code>, various required
helper functions and some pre-defined constants. Importantly this will contain
the initial definition of the <code class="language-plaintext highlighter-rouge">Block</code> data structure. You are allowed to modify
this file as needed, but it is your responsibility to make sure the changes are
compatible with the CI and the tests.</p>

  <h3 id="mymallocc">mymalloc.c<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mymallocc" aria-label="Jump to mymalloc.c" class="octicon">#</a></h3>

  <p>This file will contain your implementation of the <code class="language-plaintext highlighter-rouge">my_malloc</code> and <code class="language-plaintext highlighter-rouge">my_free</code> functions. We only provide some constants to help with your implementation. Your task will be to implement an explicit free-list allocator. We recommend using a modular approach with judicious use of helper functions as well as explanatory comments. You can insert logging calls with the <code class="language-plaintext highlighter-rouge">LOG()</code> macro we provide.</p>

  <h3 id="helper-functions">Helper functions<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#helper-functions" aria-label="Jump to Helper functions" class="octicon">#</a></h3>

  <p>We provide a number of helper functions in <code class="language-plaintext highlighter-rouge">mymalloc.h</code> and <code class="language-plaintext highlighter-rouge">mymalloc.c</code>:</p>

  <ul>
    <li><code class="language-plaintext highlighter-rouge">int is_free(Block *block)</code>: Return 1 if the given block is free, 0 if not</li>
    <li><code class="language-plaintext highlighter-rouge">size_t block_size(Block *block)</code>: Return the size of the given block</li>
    <li><code class="language-plaintext highlighter-rouge">Block *get_start_block(void)</code>: Returns the first block in memory (excluding fenceposts). If there are multiple chunks, return the first block in the first chunk.</li>
    <li><code class="language-plaintext highlighter-rouge">Block *get_next_block(Block *block)</code>: Return the next block, contiguously, in memory. If this is the last block of a chunk, return the first block of the next chunk. If this is the last chunk, return NULL.</li>
    <li><code class="language-plaintext highlighter-rouge">Block *ptr_to_block(void *ptr)</code>: Given a ptr assumed to be returned from a previous call to <code class="language-plaintext highlighter-rouge">my_malloc</code>,
 return a pointer to the start of the metadata block.</li>
  </ul>

  <p>Many of these helper functions will help you in writing various versions of the allocator. These also provide an interface for accessing and testing the internals of the allocator, as well as benchmarking. In particular, the <code class="language-plaintext highlighter-rouge">get_start_block</code> and <code class="language-plaintext highlighter-rouge">get_next_block</code> helpers will help you calculate fragmentation.</p>

  <p>Various optimisations will require you to change your implementation of these helpers:</p>
  <ul>
    <li><code class="language-plaintext highlighter-rouge">is_free</code> and <code class="language-plaintext highlighter-rouge">block_size</code> will change when you implement metadata reduction. This will also make these functions non-trivial (and actually useful).</li>
    <li><code class="language-plaintext highlighter-rouge">get_start_block</code> and <code class="language-plaintext highlighter-rouge">get_next_block</code> are sensitive to adding the multiple chunks feature. You need to track both a “first” chunk and a way to go from a given chunk to the “next” chunk.</li>
  </ul>

  <!-- TODO: add links to associated sections here when they are written -->

  <h3 id="mygch">mygc.h<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygch" aria-label="Jump to mygc.h" class="octicon">#</a></h3>
  <p>This file contains type signatures for some additional functions that are described immediately below.</p>

  <h3 id="mygcc">mygc.c<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygcc" aria-label="Jump to mygc.c" class="octicon">#</a></h3>
  <p>This file will contain your implementation of the modified versions of <code class="language-plaintext highlighter-rouge">my_malloc</code> and <code class="language-plaintext highlighter-rouge">my_free</code> to add extra elements to facilitate the GC, as well as your implementation of <code class="language-plaintext highlighter-rouge">my_gc</code>, the garbage collector. 
You are recommended to first copy in your implementations of <code class="language-plaintext highlighter-rouge">my_malloc</code> and <code class="language-plaintext highlighter-rouge">my_free</code> from the main C files, as well as
any constants and helper functions you had defined there. We also provide the function <code class="language-plaintext highlighter-rouge">get_end_of_stack()</code> and the external
variable <code class="language-plaintext highlighter-rouge">start_of_stack</code> (which we will set at the beginning of our test functions to correspond to the start of stack) to give you the endpoints of the stack for convenience.</p>

  <h3 id="mygctestc">mygctest.c<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#mygctestc" aria-label="Jump to mygctest.c" class="octicon">#</a></h3>
  <p>A file with a template <code class="language-plaintext highlighter-rouge">main()</code> function where you can insert calls to your GC and test that it frees garbage, avoids freeing reachable blocks, and so on. You are advised not to modify the initialisation of the <code class="language-plaintext highlighter-rouge">start_of_stack</code> variable in this file and use the provided <code class="language-plaintext highlighter-rouge">my_calloc_gc</code>. Add whatever you want in this file otherwise for testing your GC.</p>

  <p class="warn-box">Note that if you define your tests in seperate functions in this file and call those functions in <code class="language-plaintext highlighter-rouge">main()</code>, then because the GC includes all functions in the call stack when scanning the stack, it will include any variables you defined in <code class="language-plaintext highlighter-rouge">main()</code> when scanning. So be careful of that.</p>

  <h3 id="testpy">test.py<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testpy" aria-label="Jump to test.py" class="octicon">#</a></h3>
  <p>Script for testing your implementation.</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 test.py -h
usage: test.py [-h] [-t TEST] [--release] [--log] [-m MALLOC]

options:
  -h, --help            show this help message and exit
  -t TEST, --test TEST  test name to run
  --release             build in release mode
  --log                 build with logging
  -m MALLOC, --malloc MALLOC
                        allocator name, default to "mymalloc"
</span></code></pre></div>  </div>

  <p>The most important option is <code class="language-plaintext highlighter-rouge">-t &lt;TEST&gt;</code> which allows you to test your implementation with a single test.</p>

  <h3 id="tests">tests/<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#tests" aria-label="Jump to tests/" class="octicon">#</a></h3>
  <p>Directory with test source files and built executables. Some tests in this directory also contain explanations of what the test is doing, and potential reasons you may be failing it. You are allowed (<em>and encouraged!</em>) to write your own additional tests and add them to this file.</p>

  <h3 id="benchpy">bench.py<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchpy" aria-label="Jump to bench.py" class="octicon">#</a></h3>
  <p>Script for benchmarking your implementation. The script uses a simple benchmark from the glibc library which stresses your implementation.</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">usage: bench.py [-h] [-m MALLOC] [-i INVOCATIONS]

options:
  -h, --help            show this help message and exit
  -m MALLOC, --malloc MALLOC
                        allocator name, default to "mymalloc"
  -i INVOCATIONS, --invocations INVOCATIONS
                        number of invocations of the benchmark
</span></code></pre></div>  </div>

  <p>The default number of invocations for the benchmark is 10. If you want to perform quick benchmark runs, then you can change the number of invocations to 3 using <code class="language-plaintext highlighter-rouge">-i 3</code>. It is recommended to use at least 10 invocations if you are reporting results, however.</p>

  <h3 id="bench">bench/<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#bench" aria-label="Jump to bench/" class="octicon">#</a></h3>
  <p>Directory with benchmark source files and built executables.</p>

  <h2 id="testing">Testing<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testing" aria-label="Jump to Testing" class="octicon">#</a></h2>

  <p>You can test your implementation of malloc (assuming you have implemented your allocator in the “<code class="language-plaintext highlighter-rouge">mymalloc.c</code>” file) by simply running:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 ./test.py
</span></code></pre></div>  </div>
  <p>The above command will clean previous outputs, compile your implementation, and then run all the provided tests against your implementation. It will run all tests contained in the <code class="language-plaintext highlighter-rouge">tests/</code> folder of your repo. If you want to run a single test (such as <code class="language-plaintext highlighter-rouge">align</code>) then you can run the test script like so:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 ./test.py -t align
</span></code></pre></div>  </div>

  <p>If you have another implementation in a different file named “different_malloc.c” (for example), then you can run tests using this implementation with:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 ./test.py -m different_malloc
</span></code></pre></div>  </div>
  <p>This may be useful if you want to test a different implementation strategy or want to benchmark two different implementations (Note: <code class="language-plaintext highlighter-rouge">bench.py</code> has this same flag).</p>

  <div class="warn-box">
    <p>Note that while you are allowed to include multiple implementations of the memory allocator in different files, only the one in <code class="language-plaintext highlighter-rouge">mymalloc.c</code> will be used when running the CI tests.</p>
  </div>

  <p>If you have inserted logging calls using <code class="language-plaintext highlighter-rouge">LOG()</code>, then you can compile and run tests with logging enabled like so:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 ./test.py --log
</span></code></pre></div>  </div>
  <p>Note that some tests which compare output may fail if logging is enabled!</p>

  <p>If you want to run a single test directly (for example <code class="language-plaintext highlighter-rouge">align</code>) then you can run it like so:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">./tests/align
</span></code></pre></div>  </div>
  <p>If you have logging enabled and want to save the log for a particular test (for example <code class="language-plaintext highlighter-rouge">align</code>) to a file then you can run the following:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp">./tests/align &amp;&gt;</span><span class="w"> </span>align.log
</code></pre></div>  </div>
  <p>Make sure you don’t accidentally add the log file to your git repo as these can get quite large in size!</p>

  <p>You will almost certainly require using <code class="language-plaintext highlighter-rouge">gdb</code> at some point to debug your implementation and failing tests. You can run <code class="language-plaintext highlighter-rouge">gdb</code> directly on a test (for example <code class="language-plaintext highlighter-rouge">align</code>) like so:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">gdb ./tests/align
</span></code></pre></div>  </div>
  <p>By default the tests and your library are built with debug symbols enabled so you don’t have to fiddle with enabling debug symbols to aid your <code class="language-plaintext highlighter-rouge">gdb</code> debugging.</p>

  <p>Note also that you are allowed to (and recommended to) add extra tests for more complex cases if you like. You can do this by adding extra files in the <code class="language-plaintext highlighter-rouge">tests</code> directory containing tests, following the same format as the existing tests (make sure to use the <code class="language-plaintext highlighter-rouge">mallocing</code> and <code class="language-plaintext highlighter-rouge">freeing</code> wrappers provided in <code class="language-plaintext highlighter-rouge">testing.h</code> as well). These extra tests should be automatically included when running <code class="language-plaintext highlighter-rouge">test.py</code>. Writing extra tests is especially helpful if you find the benchmark script <code class="language-plaintext highlighter-rouge">bench.py</code> to be crashing.</p>

  <h3 id="internal-testing">Internal testing<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#internal-testing" aria-label="Jump to Internal testing" class="octicon">#</a></h3>

  <p>In addition to tests which verify the malloc interface itself works, and things like data consistency (data written to a block stays consistent and does not interrupt metadata), we provide a few tests which use the helper functions you’ve written to verify the internal workings of malloc and/or particular parts of it. This should help further pinpoint errors in your code in some simple cases. Note that these tests <em>require</em> you to have used the helper functions we provided you and implemented them correctly. These tests reside in the <code class="language-plaintext highlighter-rouge">internal-scripts</code> directory and are also run by <code class="language-plaintext highlighter-rouge">test.py</code>, and you can add more yourself too.</p>

  <p>Note that it is possible for you to have designed an optimisation in a way which causes one of these tests to fail even when nothing is actually wrong due to the test expecting certain internal behavior. If this occurs, as long as you are confident it is not an implementation issue, it is not a problem; just mention this in your report.</p>

  <h3 id="address-sanitizer">Address sanitizer<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#address-sanitizer" aria-label="Jump to Address sanitizer" class="octicon">#</a></h3>

  <p>The Makefile we have provided uses the GCC flag <code class="language-plaintext highlighter-rouge">-fsanitize=address</code>. This enables the AddressSanitizer which instruments mmeory accesses to detect memory errors at runtime, such as access to unallocated memory. You can read more about it here: https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html. You may see output from “asan” in your test output as a result of this. Hopefully this will help you debug some of your memory-related bugs in this assignment.</p>

  <h3 id="testing-the-gc">Testing the GC<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#testing-the-gc" aria-label="Jump to Testing the GC" class="octicon">#</a></h3>

  <p>The <code class="language-plaintext highlighter-rouge">test.py</code> script does not include tests for the GC, but you can write your 
own tests in <code class="language-plaintext highlighter-rouge">mygctest.c</code> if you’d like. 
You will have to modify the <code class="language-plaintext highlighter-rouge">Makefile</code> to compile and run the GC tests you write yourself.</p>

  <p class="info-box">There will be additional test cases we use when marking your code that are not given to you in the assignment repository for both <code class="language-plaintext highlighter-rouge">mygc</code> and <code class="language-plaintext highlighter-rouge">mymalloc</code>.</p>

  <h2 id="benchmarking">Benchmarking<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking" aria-label="Jump to Benchmarking" class="octicon">#</a></h2>

  <h3 id="benchmarking-execution-time">Benchmarking execution time<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking-execution-time" aria-label="Jump to Benchmarking execution time" class="octicon">#</a></h3>

  <p>If you want to benchmark your code, then you will have to install some python libraries, namely <code class="language-plaintext highlighter-rouge">numpy</code> and <code class="language-plaintext highlighter-rouge">scipy</code>. This can be achieved by using <code class="language-plaintext highlighter-rouge">pip3</code>, python’s package manager:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">pip3 install numpy scipy
</span></code></pre></div>  </div>
  <p>This will install the two libraries to your local user (as opposed to system-wide). This is the recommended method for installing per-user packages for python.</p>

  <p>Benchmarking your code works in a similar way as testing:</p>

  <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="go">python3 ./bench.py
</span></code></pre></div>  </div>
  <p>This will run the provided benchmark (<code class="language-plaintext highlighter-rouge">bench/benchmark.c</code>) from glibc 10 times and provide you the average. If you are benchmarking, it is <strong><em>highly</em></strong> recommended to close all other intensive applications on your machine as you may get random interference otherwise. If you want to report your benchmark numbers, it is important to note what CPU and memory speed you were using in your report.</p>

  <p>Just like the test script, you can switch the malloc implementation using the <code class="language-plaintext highlighter-rouge">-m &lt;MALLOC&gt;</code> flag. This is useful as you may want to have two different implementations that you want to compare performance on.</p>

  <p>If you have time, you might also find interesting results by experimenting with the sizes/number of mallocs done by the benchmark.</p>

  <h3 id="benchmarking-fragmentation">Benchmarking fragmentation<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#benchmarking-fragmentation" aria-label="Jump to Benchmarking fragmentation" class="octicon">#</a></h3>

  <p>For benchmarking fragmentation, we provide the internal test <code class="language-plaintext highlighter-rouge">internal-scripts/fragmentation.c</code>. This tests provides a number of random allocations and frees. There is then a space in the code containing a TODO where you are able to calculate fragmentation and report it. You can run this script the same way as the other tests (<code class="language-plaintext highlighter-rouge">test.py</code>).</p>

  <p>As described earlier, how exactly you calculate fragmentation is up to you, but we require that you implement at least the peak memory utilisation metric described in lectures.</p>

  <p>If you have time, you might also find interesting results by experimenting with the compile time constants at the top of the file.</p>

  <h2 id="submitting-your-work">Submitting your work<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#submitting-your-work" aria-label="Jump to Submitting your work" class="octicon">#</a></h2>
  <p>Submit your work through <code class="language-plaintext highlighter-rouge">Gitlab</code> by pushing changes to your fork of the assignment repository. A marker account should automatically have been added to your fork of the Assignment 1 repo (if it isn’t there under “Members” then let one of your tutors know).</p>

  <p>We recommend maintaining good <code class="language-plaintext highlighter-rouge">git</code> hygiene by having descriptive commit messages and committing and pushing your work regularly. We will not accept late submissions.</p>

  <h2 id="submission-checklist">Submission checklist<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#submission-checklist" aria-label="Jump to Submission checklist" class="octicon">#</a></h2>

  <ul>
    <li>The code with your implementation of malloc in <code class="language-plaintext highlighter-rouge">mymalloc.c</code>.</li>
    <li>The code with your implementation of the GC in <code class="language-plaintext highlighter-rouge">mygc.c</code></li>
    <li>The <code class="language-plaintext highlighter-rouge">report.md</code> is in the top-level directory.</li>
    <li>(Optional) Any optional tests and benchmrks you want us to look at.</li>
    <li>Your <code class="language-plaintext highlighter-rouge">statement-of-originality.md</code> has been filled out correctly.</li>
  </ul>

  <h2 id="ci-artifacts">Gitlab CI and Artifacts<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#ci-artifacts" aria-label="Jump to Gitlab CI and Artifacts" class="octicon">#</a></h2>

  <p>For this assignment, we provide a CI pipeline that tests your code using the same tests 
available to you in the assignment repository. It is important to check the results of the 
CI when you make changes to your work and push them to GitLab. This is especially 
important in the case where your tests are passing on your local machine, but not on the CI - 
it is possible your code is making incorrect assumptions about the machine your 
memory allocator is running on. If you’re failing tests in the CI then it is best 
to have a look at the CI results for these tests and see if they are giving you hints as to why.</p>

  <p><a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/ci-icon-image"></a></p>

  <p>To view the CI pipeline for your repo, click on the little icon to the right of your most recent commit.</p>

  <p><img src="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/ci-icon.png" alt="ci icon"></p>

  <p><img src="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/job-status.png" alt="ci job status"></p>

  <h3 id="pdf-artifact">PDF Artifact<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#pdf-artifact" aria-label="Jump to PDF Artifact" class="octicon">#</a></h3>
  <p>Your repo will be packaged into a pdf for marking purposes. As such it is important that you see what the result 
of the <code class="language-plaintext highlighter-rouge">pdf</code> job is and make sure the output makes sense.</p>

  <p>It will:</p>
  <ul>
    <li>take your name and uid from the <code class="language-plaintext highlighter-rouge">statement-of-originality.md</code></li>
    <li>take the results of the provided CI tests</li>
    <li>take your report written in the <code class="language-plaintext highlighter-rouge">report.md</code> file</li>
    <li>take test results from the CI</li>
    <li>take references from the <code class="language-plaintext highlighter-rouge">statement-of-originality.md</code></li>
  </ul>

  <p>To view the pdf, first click the ci icon on your most recent commit (<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#ci-icon-image">as above</a>), then click on the
<code class="language-plaintext highlighter-rouge">pdf</code> job.</p>

  <p>Then, you’ll be taken to the job page, where you should see a “Job Artifacts” section, click on the <code class="language-plaintext highlighter-rouge">Browse</code> button.</p>

  <p><img src="/Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/pdf-job.png" alt="pdf job"></p>

  <p>Click on the file to preview what your pdf looks like:</p>

  <p><img src="/Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/browse-preview-pdf.png" alt="pdf preview"></p>

  <p>Which should look something like this:</p>

  <p><img src="/Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/pdf-example.png" alt="pdf example"></p>

  <p>Your report should appear if you scroll down to the next page.</p>

</div>
<div class="footnotes" role="doc-endnotes">
  <ol>
    <li id="fn:1" role="doc-endnote">
      <p>The number of free lists you are required to use is given by the <code class="language-plaintext highlighter-rouge">N_LISTS</code> constant in <code class="language-plaintext highlighter-rouge">my_malloc.h</code> (set to 59).&nbsp;<a href="https://comp.anu.edu.au/courses/comp2310/assessments/01-malloc/#fnref:1" class="reversefootnote" role="doc-backlink">↩</a></p>
    </li>
  </ol>
</div>


        
        
      </section>

      
      

      
      

    </div>
  </main>

  
  

  <div class="container filler"></div>
</div>

    

    










<article>
  <div class="container footer__socials-container">
    <article>
      <nav aria-label="Social links" class="footer__socials">
        
        
  
        
        
  
        
        
  
        
        
  
        
        
  
        
        
      </nav>
      </article>
  </div>
</article>

<footer class="anu-wf-footer" aria-label="Footer banner" role="contentinfo" data-tracker="anu"></footer>
<script src="./Assignment 1_ Malloc _ Systems, Networks, and Concurrency_files/bundle.js.下载"></script></body></html>